Names in Boxes
One hundred people play the following game. Their names are written on pieces of paper and put into 100 labeled boxes at random. Each box is labeled with a number from 1 to 100 and one name has been placed inside each box. The boxes are placed on a table in a separate room. The players go into the room one by one and each has to open 99 boxes one after another. After each player finishes and leaves the room, the boxes are closed again. The players are not allowed to communicate with each other in any way, although they have been given one day before the event to discuss their strategies. They only win if every one of the one hundred players avoids opening the box with his or her own name. What is the optimal strategy?
Let me first discuss a simpler version of the game. Each player has to open exactly one box and they win if each one of them finds their name. After each player finishes and leaves the room, the boxes are closed again and the room is re-set.
If all of them decide to open box number 42, they are guaranteed to lose. They can try to open random boxes, then they win with probability (1/100)100. Can they use a joint strategy that is better than random?
Yes, they can. Clearly, two people shouldn’t open the same box. So on the day before, if each agrees to open a box with a different assigned number, their probability to win is one over 100!. I leave it to my readers to prove that this is the best strategy.
What is the difference between this problem and the original problem? Isn’t choosing the last box the same as choosing the first? Aha! When they open 99 boxes they see the names, so they can use this information as part of their strategy.
I hope that this new version is so intriguing that you will start solving this puzzle right away.
Share:
Leo:
Is there a strategy that is gives >1% probability of winning?
4 April 2012, 1:13 pmed:
I don’t think you can get >1%, but you can get 1% exactly.
This is closely related to the puzzle where everybody gets 50 tries to find their own name, discussed here among other places:
https://ocfnash.wordpress.com/2009/12/12/pity-the-prisoners/
4 April 2012, 6:34 pmAndrew MW:
Is the first person allowed to
4 April 2012, 6:45 pm(1) change the arrangement of the boxes in the room, or
(2) swap names between boxes?
Tanya Khovanova:
Andrew,
No the first person is not allowed to do that. That would be a form of communicating.
4 April 2012, 11:08 pmLeo:
ed: Sure, that’s what I had in mind.
5 April 2012, 12:02 amOMF:
Do the players know the order in which they will be let into the room?
In addition, do the players know when a player before them has failed?
5 April 2012, 2:38 pmTanya Khovanova:
OMF,
No communication of any kind is allowed.
5 April 2012, 8:45 pmOMF:
Then I think there is no optimal strategy. The boxes are labelled at random and the trials are completely random, so the names within the boxes contain no information about the problem of any use to the players. The player in the end can only choose one box not to open, or an algorithm which ultimately must choose such a box at random from the set. Therefore, I think that the two problems are equivalent.
To prove the original problem has probability 1/100!:
Each player must open only one box, and the players win if they all find their own names. Lets say the players choose one box to open beforehand. Since the boxes are random, any choice is equivalent to picking the boxes in order. So player 1 pixes box 1, player 2 box 2, etc. In order for the players to win, player 1 must win AND player 2 must win AND…etc
The odds of player 1 winning are 1/100. After this, player 2s odds are 1/99. Player 3’s odds 1/98, etc.
So the odds of winning with this strategy are
1/100*1/99*1/98*…..*1/2*1/1=1/(100!)
But the odds of guessing the correct permutation of 100 objects is also 1/100!, which is what this problem amounts to. Therefore choosing boxes beforehand is the optimal strategy, for both problems.
Since 100! is greater than the number of known atoms in the universe, the odds of winning are not very good.
6 April 2012, 7:54 pmJoseph:
OMF: I disagree with the phrase “the names within the boxes contain no information about the problem of any use to the players.”
Then again, I’d probably agree with you, if I hadn’t already seen the answer to this problem. 😀
7 April 2012, 11:51 amChrist Schlacta:
Only possible if there’s some pattern in the namenumber correlation, such as if the “random” pattern is to sort by last,first, then place them in boxes in order. If the boxes are in order, and every person knows the name of every other, than the odds of winning can be increased to approximately 100%, minus the initial guess of 1/100 odds of accidentally picking their own name on one of the first few draws prior to knowing it’s alphabetized.
9 April 2012, 2:31 pmAlternatively, if the players have the option, each can specify a false name, then when the challenge time arrives, each can specify their real name. Assuming no user specifies a real person’s name as their false name, then the game can be won 100% of the time.
Greg:
As stated in the puzzle, it’s truly random and there is no communication between players at the game (in fact 100 identical rooms can be set up and the players can do the choosing all at the same time). I cannot work out how the idea mentioned by Leo and ed can apply to this puzzle, not to mention that 1% seems highly unlikely here. Anyway, I see that there is a strategy that can achieve 2/100! odds. But that seems to be such a small improvement over 1/100!. Is there anything better?
9 April 2012, 11:56 pmsaar:
for example let us begin with only 3 people/
10 April 2012, 4:21 amlet each begin with another box. if the first opens box 1, if he find 1, they lost, but if he finds 2 then he knows that boxes 2 and 3 there are names 1 and 3, but if in box 3 there is name 3, anyhow they will lose, so he can decide that his name is in box 3, and he will open it.
the same if he finds in box 1 name 3, he will open box 2
now the chance to win is 1/3, much more then 1/6/
ed:
To clarify, my claim is you can win with prob 1/n in the first version of the puzzle, the one where you open n-1 boxes and try to NOT find your name. The link I provided gives a strong hint, by solving a related puzzle.
12 April 2012, 10:15 pmOMF:
Saar, I don’t see how your solution can work. You say that each player first picks the box corressponding to their own name, then another based on the choices of the other players, etc.
But since the entire experiment is completely random, the boxes can all be relabelled at random in each trial without changing the probabilities of each individual player succeeding. Since winning is conditional on all players winning, I don’t think such a strategy will improve the odds.
Ultimately it boils down to picking the correct permutation of 100 objects—or so I conclude at least.
15 April 2012, 11:09 pmsaar:
i am sorry, english is not my laguage/
if we take the 6 posibilities for 3 people
123
132
213
231
312
321
we can agree that we will lose in {123, 132, 213, 321} but ensure that in casas {231, 312} we will win. eace of the people will know, when he opens his number’s box, which from these posibilities is surely wrong, and will ensure that if the other is right, they will not lose.
the same for 100 people. if we agree about the first box each open, we will try just to ensure cases that are not koses cases from begining
18 April 2012, 6:12 amChris Chang:
For everyone here who doesn’t see how to achieve 1% probability of success:
Assign each person a number 1-100; each person starts by opening the box labeled with their assigned number. If they don’t immediately lose, they move on to the box labeled with the number corresponding to the name they just saw.
This will succeed as long as the name permutation consists of only a single giant cycle, which happens 1% of the time (quick exercise: prove this if you haven’t seen this result before).
The next question is: can you prove this is optimal?
12 May 2012, 3:29 am